\subsection{Signatures numériques}
En 1976, W. Diffie et M. Hellman ont souligné l'importance de mettre au point une signature numérique qui, à l'instar d'une signature manuscrite, garantirait l'authenticité, l'intégrité et la non répudiation d'un message signé, en particulier dans un système de plus en plus informatisé où l'authentification des documents est fondamentale pour son équilibre.

\subsubsection{Propriétés des signatures numériques}
Une signature est une chaîne de caractères qui dépend d'un secret et du contenu du message soumis à la signature. Garantir l'intégrité d'un document numérique et l'authentification de son auteur sans que celui-ci puisse répudier sa signature suppose que seul le signataire peut réaliser la signature(personne ne peut forger la signature), alors que tout le monde doit pouvoir vérifier celle-ci.\\
De manière générale pour garantir la sécurité d'une signature on exigera qu'étant donnés $M_1,M_2,...,M_k$ $k$ messages choisis par l'attaquant et $S_1,S_2,...,S_k$ les signatures valides de ces $k$ messages, il doit être calculatoirement difficile de trouver $M'$' n'appartenant pas à ces messages et une valeur $S'$ qui soit une signature valide de $M'$.\\

Une signature numérique ne peut donc s'envisager que dans un schéma asymétrique. Pour signer, il faut alors :\\
\begin{enumerate}
\item une clé privée que nous noterons $SK$ pour "Secret Key" ou $PrK$ pour "Private Key".
\item une clé publique associées à  $SK$. Nous la noterons $PK$ ou $PuK$ pour "Public Key".
\item un algorithme $sign$ pour générer la signature. Ainsi la signature $S$ d'un message $data$ vaudra $S = sign_{SK}(data)$.
\item un algorithme de vérification $verif_{PK}(S,data)$ qui renvoie vrai ou faux. 
\end{enumerate}
Le détenteur légitime de la clé privée est le seul à pouvoir produire une signature valide.  
Si cela permet d'assurer l'authentification et la non répudiation, cela ne suffit pas à garantir la non forgeabilité de cette signature. Il faut en effet condensé le message à signer, c'est à dire que $data$ est le "haché" du message : $data=H(message)$, où $H$ est une fonction de hachage cryptographique. Les fonctions de hachage standards sont SHA et MD5, même si des collisions ont été découvertes pour MD5 et SHA1. SHA 256 est à privilégier.

\subsection{Protocole de signature DSA}
Le protocole de signature digital signature algorithm (DSA) s'inspire du schéma de signature d'El Gamal. Il consiste à travailler dans un sous-groupe d'ordre $q$ de $\mathbb{Z} / p \mathbb{Z}$ tout en appliquant une composition d'une réduction modulo $p$ puis d'une réduction modulo $q$ afin de complexifier la sécurité du schéma.\\
\begin{enumerate}
\item Génération des clés :\\
Soit Alice un signataire. Alice choisit
	\begin{itemize}
	\item un nombre premier $p$,  
	\item $q$ un nombre premier diviseur de $p-1$,
	\item $g$ appartenant à $\mathbb{Z} / p \mathbb{Z}$
	\item une fonction de hachage $H$
	\end{itemize}	 
Alice choisit ensuite de manière aléatoire $x$ un élément de $\mathbb{Z} / q \mathbb{Z}$.\\
Alice calcule $y=g^x \mod p$.\\
Le quadruplet $(p,q,g,y)$ constitue la clé publique associée à $x$ clé secrète.
\pagebreak
\item Signature :\\
Soit $M$ le message qu'Alice veut signer. Alice doit alors :
\begin{itemize}
\item choisir aléatoirement un élément $k$ de $\mathbb{Z} / q \mathbb{Z}$.
\item calculer $r=g^k \mod p \mod q$.
\item calculer $s=(H(M)+rx) \ast k^{-1} \mod q $
$(r,s)$ représente alors la signature du message $M$
\end{itemize}

\item Vérification :\\
Pour vérifier que le couple $(r,s)$ représente une signature valide pour le message $M$, il faut alors s'assurer que les deux conditions suivantes sont établies :
\begin{itemize}
\item $(r,s)$ appartient à $\mathbb{Z}q^2$
\item $r = g^{H(M)s^{-1}}y^{rs^{-1}} \mod p \mod q$
\end{itemize}
\end{enumerate}

\subsection{Signatures avec courbes elliptiques}
L'algorithme Elliptic Curve Digital Signature Algorithm (ECDSA) proposé au NIST par Scott VANSTONE en 1992, a été standardisé en 1998 sous le standard X9.62-1998, Public Key Cryptography For The FInancial Services Industry. Cet algorithme reprend les principes du standard DSA mais offre, pour des clefs de longueurs plus courtes, une sécurité identique à DSA tout en raccourcissant les temps de calculs.

\subsubsection{Définition d'une courbe elliptique}
On appelle courbe elliptique sur une corps de gallois noté $ GF(p)$
l'ensemble des points $(x,y)$ qui satisfont l'équation de la forme $y^2=x^3+Ax+B$, où $x$, $y$, $A$, $B$ appartiennent à $\mathbb{Z} / p \mathbb{Z}$ et $4 \ast A^3 + 27 \ast B^2 \neq 0 \mod p$  

\subsubsection{Propriété d'une courbe elliptique}
Soit $E$ une courbe elliptique, $(E,+)$ est un groupe. En effet :
\begin{itemize}
\item $+$ est une loi interne associative
\item $\vartheta$ (infini) est élément neutre de $E$
\item tout élément appartenant à E possède un symétrique
\end{itemize}
 
\subsubsection{Addition de deux points d'une courbe elliptique} 

Soient deux points $P$ et $Q$ / $R=P+Q$ \\
$
\begin{array}{l}
u=(y_q-y_p) \times (x_q-x_p)^{-1}\mod p    \\
v=(y_p-u \times x_p) \\ x_r= u^2-x_p-x_q \\ y_r=-(u \times x_r + v)  \\
\end{array}$

\subsubsection{Calcul des coordonnées d'un point d'une courbe elliptique}
A l'instar de la signature ElGamal, le schéma de signature ECDSA repose sur le logarithme discret. Mais, a contrario d'ElGamal, qui utilise un groupe multiplicatif, il faut, dans le cas des courbes elliptiques, considérer cette fois la loi additive $+$ et $\underbrace{G+G+G+ \ldots +G}_a = aG$ au lieu de $G^a=\underbrace{G \cdot G \cdot G \ldots G }_a$. \\
\pagebreak

Au lieu de calculer $P^a$, il faut maintenant calculer $a \cdot P$ en utilisant l'algorithme double and add : 

\begin{algorithm}[!h]
\centering
\begin{algorithmic}
\STATE{Décomposition préalable :} 
\STATE{$ a= \sum_{k=0}^n a_k 2^k$}\\
\STATE{Initialisation :}
\STATE{$Q \leftarrow 0$}
\FOR{k de n à 0 }
	\STATE{$Q \leftarrow 2Q$}
	\IF{($a_k = 1$)}
	\STATE {$Q \leftarrow Q + P$}
	\ENDIF
\ENDFOR
\end{algorithmic} 
\caption{Calcul de coordonnées d'un point d'une courbe elliptique}
\label{algo:algo1}
\end{algorithm}

Les courbes elliptiques,permettent l'utilisation de clés nettement plus petites que celles des algorithmes classiques ($2 \times 160$ bits pour les coordonnées contre 1024 bits), pour un niveau de sécurité équivalent. 

\subsubsection{Signature avec courbe elliptique}

\begin{itemize}
\item Soit $M$ le message qu'Alice souhaite signer avec une courbe elliptique.
\item Soit $H$ une fonction de hachage cryptographique.
\item Considérons une courbe elliptique $E$ et G un point de cette courbe d'ordre $p$, où $p$ est un nombre premier. 
\end{itemize}

\begin{enumerate}

\item Génération des clés :
	\begin{itemize}
	\item Alice tire aléatoirement $s$ entre $1$ et $p-1$
	\item Alice calcule ensuite $Q=sG$
	\end{itemize}
$Q$ représente la clé publique et $s$ la clé secrète.

\item Signature :
	\begin{itemize}
	\item Alice tire aléatoirement $k$ entre $1$ et $p-1$.
	\item Alice calcule ensuite les coordonnées $(i,j)$ du point $kG$.
	\item Il faut alors évaluer $x = i \mod p$.
	\item Alice calcule alors $y = k^{-1}(H(M) + sx)\mod p$
	\item Si $x$ ou $y$ prend une valeur nulle, alors il faut retirer un entier $k$ et refaire les calculs de $x$ et $y$.
	\end{itemize}
Le couple $(x,y)$ représente alors la signature du message.

\item Vérification :\\
Lorsque Bob reçoit le message d'Alice, celui-ci doit alors:
	\begin{itemize}
	\item Vérifier que $(x,y)$ appartient à $\mathbb{Z}^2_p$
	\item Calculer $(H(M)y^{-1} \mod p)G + (xy^{-1}\mod p)Q$ pour retrouver $(i,j)$
	\item Vérifier que $x = i \mod p$
	\item Vérifier que Q est un bien un point de la courbe elliptique non nul et que $nQ=(0,0)$	
	\end{itemize}
\end{enumerate}
\pagebreak

\subsubsection{Validité du schéma de signature}
Démontrons que si $x=i \mod p$ alors on vérifie bien la signature. \\

Pour cela calculons $(H(M)y^{-1} \mod p)G + (xy^{-1}\mod p)Q$.\\

$(H(M)y^{-1} \mod p)G + (xy^{-1}\mod p)Q = (H(M)y^{-1} \mod p)G + (xy^{-1}\mod p)sG$ par définition de $Q$.\\

En factorisant par $G$ on obtient :
$$(H(M)y^{-1} \mod p)G + (xy^{-1}\mod p)Q = ((H(M)y^{-1}+sxy^{-1})\mod p)G$$ 

Soit encore :
$$(H(M)y^{-1} \mod p)G + (xy^{-1}\mod p)Q = ((H(M)+sx)y^{-1}\mod p)G$$ 

Or $y = k^{-1}(H(M) + sx)\mod p$\\

Donc en inversant $y$, on peut écrire :
$$(H(M)y^{-1} \mod p)G + (xy^{-1}\mod p)Q = ((H(M)+sx)k(H(M)+sx)^{-1})\mod p)G = (k \mod p)G = kG$$

Ainsi on end déduit bien que :
$$(H(M)y^{-1} \mod p)G + (xy^{-1}\mod p)Q = kG = (i,j)$$

La signature est donc bien vérifiée si $x=i \mod p$.

\subsubsection{Sécurité du schéma de chiffrement avec courbe elliptique}
La sécurité du schéma de chiffrement DSA se fonde sur la complexité du logarithme discret dans un groupe fini multiplicatif. Ceci est toujours le cas dans le cadre des courbes elliptiques, mais avec la loi additive.\\
Différentes méthodes existent pour résoudre le logarithme discret comme l'algorithme "pas de géant, pas de bébé" ou la méthode "$\rho$-Pollard". Le meilleur algorithme pour résoudre ce problème est en $\mathcal{O}(\sqrt{p})$ où $p$ est l'ordre du groupe considéré. Ainsi, alors qu'avec le DSA "classique", utilisant des groupes tels que $\mathbb{Z} / p \mathbb{Z}$ avec $p$ un nombre premier de l'ordre de $2^{1000}$, les courbes elliptiques permettent de réduire la taille des nombres à $2^{200}$ environ.    



\subsection{Notions de certificats}
De manière générale une transaction ne peut se faire que si une relation de confiance a été établie. Cela implique que l'identité des acteurs doit être liés aux clés cryptographiques utilisées. Afin de lier une identité à une clé, il faut utiliser : 

Afin de lier une identité à une clé, il faut utiliser :
\begin{itemize}
\item la diversification dans le cadre de la cryptographie symétrique
\item la certification dans le cas asymétrique, c'est celui qui nous intéresse.
\end{itemize}

Dans une infrastructure à clé publique (PKI), basée sur des algorithmes de chiffrement asymétriques, il s'agit de partager entre les utilisateurs une clé publique. Le partage de cette clé publique peut se faire grâce à l'utilisation d'un serveur (comme cela se ferait en entreprise), ou bien la clé peut être transmise par l'utilisateur à qui correspond cette clef publique (comme cela peut être le cas avec une carte à puce).\\
Pour garantir le lien entre cette clé publique et l'utilisateur associé, un tiers de confiance, appelé autorité de certification,est nécessaire. Cette autorité délivre à cet effet un certificat avec une date de validité. Elle peut également, en cas de compromission, révoquer le certificat.\\

 
La certification va permettre à un individu, appelons le Alice, d'être \textit{authentifié} , par un serveur par exemple. elle va également lui permettre de signer un message transmis à un interlocuteur, Bob , qui va \textit{vérifier cette signature}. Enfin, ce même Bob pourra, grâce au certificat, \textit{chiffrer} un message que seul Alice pourra déchiffrer.\\

Pour réaliser un certificat liant une identité à une clé publique, il faut tout d'abord appliquer une fonction de hashage à ces deux éléments, puis faire passer le résultat obtenu dans un algorithme de signature reposant sur RSA ou les courbes elliptiques.Cette signature nécessite l'utilisation d'une clé fournie par un tiers de certification qui atteste de sa légitimité. Le trio (identité, clé, signature) forme un certificat.\\

L'utilisation du certificat peut se faire :\\

Utilisation du certificat :\\

\begin{itemize}
\item en signature ou authentification :\\
Lorsque Alice veut être authentifiée par Bob ou lui envoyer un message signé, elle lui envoie également son certificat. Bob doit tout d'abord consulter la liste de révocation du tiers de certification, si le certificat n'est pas révoqué, Bob peut le \textit{vérifier} avec la clé publique du tiers.\\
 Il peut alors en déduire la clé publique de Alice et peut l'utiliser pour vérifier la signature du message ou réaliser l'authentification de Alice.
\item en chiffrement :\\ 
Après avoir vérifié le certificat, Bob utilise un algorithme de chiffrement utilisant la clé publique de Alice pour chiffrer un message. Seule Alice pourra le déchiffrer avec sa clé privée. 
\end{itemize}